/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A)
    {
        struct ListNode* slow, * fast, * tmp, * cur, * head;
        head = slow = fast = A;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        cur = slow;
        slow = nullptr;
        while (cur)
        {
            tmp = cur->next;
            cur->next = slow;
            slow = cur;
            cur = tmp;
        }
        while (slow)
        {
            if (slow->val != head->val)
            {
                return false;
            }
            slow = slow->next;
            head = head->next;
        }
        return true;
    }
};